Field programmable gate arrays (FPGAs) are widely used in the design of the logic circuits, recently (reference 1). An FPGA is a PLD that can change interconnections among logic cells (Configurable Logic Block: CLB) arranged in a two-dimensional matrix by rewriting the memory. FPGAs work as hardware, and are different from microprocessors (MPUs) that operate software programs. Thus, a feature of FPGAs is their fast manipulation of logic functions.
On the other hand, in FPGAs, we can change physical interconnections between CLBs by programming. Therefore, the physical design to reduce interconnection delay is necessary, and such work is a time-consuming work. Moreover, since the delay depends on interconnections between CLBs, the interconnections delay is hard to predict without finishing the layout. Therefore, the performance estimation of the logic circuits is difficult during logic design.
Moreover, the fraction of the area for interconnections on the chip will be very large, since in FPGAs, the free interconnections among CLBs arranged in two-dimensional array are necessary. Moreover, since pass transistors are used for the interconnections, the delay of the interconnection part is fairly large.
Thus, LUT cascade has been proposed as a PLD that resolves above-mentioned demerits of FPGAs (reference 2 and 3). An LUT cascade is obtained by a series connection of LUTs. The LUT cascade can be represented as a series connection of LUTs that represent the decomposed functions of the object logic function. The LUT cascade is different from the FPGA, since the FPGA realizes logic functions by the networks of CLBs arranged in two-dimensional array, while the LUT cascade realizes logic functions arranged in a one-dimensional network of LUTs.
Each CLB used in an FPGA realizes a basic logic gate. The basic design concept of FPGA is to realize a complex logic circuit by connecting these basic logic gates. Therefore, in FPGA, the interconnection circuit to connect CLBs arranged in two-dimensional array is inevitable. An FPGA requires a large area for interconnections in addition to the area for logic. Thus, the chip area of FPGA tends to be large.
On the other hand, the basic design concept of an LUT cascade is to realize complex logic function by a series connection (one-dimensional array) of LUTs that realize complex multiple-output logic functions. Therefore, each LUT has, in general, many inputs and many outputs. Since two-dimensional interconnection circuit is unnecessary, the area for interconnections is fairly small, and the most of the chip area is spent for the memory area to store LUTs.
Moreover, in an LUT cascade, the chip area for the interconnections, and the delay time for the interconnections are smaller than that of FPGAs.
From here, we will explain a design method of the LUT cascade. FIG. 52 shows the principle of the LUT cascade. For simplicity, we use an example of an LUT cascade without intermediate outputs.
To design a LUT cascade for a given logic function, first, we decompose the objective function ƒ(X) into s subfunctions {ƒi(Xi); i=0, . . . , s−1} (s≧2). Here, X=(χ0, . . . , χn−1) denotes an ordered set of the input variables. The unordered set of the input variables is denoted by {X}. Here, {X}={X0}∪ . . . ∪{Xs−1}{Xi}∩{Xj}=φ(i≠j; i, jε{0, . . . , s−1}). The output variables of each decomposition function ƒi (in general, vector) are denoted by Yi+1. Hereafter, the number of variables in X and Y are denoted by |X| and |Y|, respectively. Especially, |X|=n, |Xi|=ni, and |Yi|=ui.
Let k be the number of input variables of decomposition functions F0. We consider to decompose the objective logic function ƒ(X) into s subfunctions, ƒ0(X0), ƒ1(X1), . . . , ƒs−1(Xs−1), where n0=k and ni=k−ui (0<i<s−1) and ns−1=k−us−1−t(0≦t≦k−2) (references 2 and 3). In this case, the objective logic function ƒ(X) is decomposed into (s−1) subfunctions ƒj(jε{0, . . . , s−2}) of k variables, and one subfunction ƒs−1 of (k−t) variables. Then, we represent these subfunctions ƒr(rε{0, . . . , s−1}) by truth tables and implement them by LUTs (look up tables). Decomposition can be found by using decomposition chart. The decomposition chart of objective logic function ƒ(X1,X2) has 2|X2| rows and 2|X1| columns, with distinct labels of a binary code in the each row and the each column of the table, and the corresponding element of the table shows the truth value of the function ƒ(X1,X2).
In FIG. 52, s copies of LUTs (LUT0 through LUTs−1) represent decomposition functions {ƒi; i=0, . . . , s−1}. Each LUT (LUTr) can be implemented by a memory with k input and ur+1 output. Such memory is denoted by “Memory for logic.” By connecting memories for logic in cascade, we have the LUT cascade shown in FIG. 52.
In the LUT cascade, when the number of inputs and outputs of the objective logic function ƒ(X) is large, we need many LUTs to implement ƒ(X). Therefore, the operation speed of an LUT cascade can be slower than an optimally designed FPGA. However, the operation of each subfunction is done in high speed by a table lookup of a memory in the LUT cascade. Thus, the operation speed of LUT cascade can be faster than software that runs on an MPU.
The operation speed of the cascade is easily estimated by the number of levels of an LUT. Therefore, we can accurately estimate the performance of the cascade during the logic design. Moreover, the interconnections are only between adjacent memories for logic in the LUT cascade. Thus, the influence of the interconnection delays need not be considered at the design of the logic circuit. Therefore, the design of LUT cascade is easier than FPGA.
However, when we implement an objective logic function by an LUT cascade shown in FIG. 52, the number of input and the number of rail outputs (number of lines between adjacent LUTs) of a memory for logic, depends on the function to be realized. Thus, to implement a wide range of functions, we have to prepare different LUT cascades having cells with different number of inputs, and different number of rail outputs. But, this is not so convenient.
To make a PLD to realize wider range of functions, one could use memories with enough number of inputs. However, the size of the memory will be double when the number of inputs is increased by one. Therefore, such strategy will increase unused memory. Moreover, the chip area for the memory increases as the memory increases. And, the compact implementation will be difficult, and the power consumption increase, too.
The purpose of the present invention is to provide a PLD that can change the number of input lines and the number of rails of memory for logic according to the objective function to make the size of memory minimum.